package algo;

import java.util.ArrayList;

public class Algo {

	private int source;
	private int sourceInit = 0;
	private ArrayList<Integer>[] listAdja;
	private ArrayList<Integer> res;

	public Algo(ArrayList<Integer>[] l){
		source = 0;
		listAdja = l;
		res = new ArrayList<Integer>();
	}

	public void deleteArete(int point1, int point2){
		boolean test = true;
		int i=0;
		while(test && i<listAdja[point1].size()){
			if(listAdja[point1].get(i) == point2){
				listAdja[point1].remove(i);
				test = false;
			}
			i++;
		}
		test = true;
		i = 0;
		while(test && i<listAdja[point2].size()){
			if(listAdja[point2].get(i) == point1){
				listAdja[point2].remove(i);
				test = false;
			}
			i++;
		}
	}

	public boolean execution_v2(){
		res.add(source);
		if(isEulerien()){
			while(listAdja[sourceInit].size() != 0){

				int i = 0;
				boolean trouve = false;
				boolean outLength = false;
				while(!(trouve) && !(outLength)){
					if(parcoursLargeur(source, listAdja[source].get(i))){
						trouve = true;
					}
					if(i<listAdja[source].size()){
						outLength = true;
					}
					i++;
				}
				i--;

				if(trouve){
					int tmp = listAdja[source].get(i);
					deleteArete(source, listAdja[source].get(i));
					source = tmp;
					res.add(source);
				}else if(outLength){
					
					int tmp = listAdja[source].get(listAdja[source].size()-1);
					deleteArete(source, listAdja[source].get(listAdja[source].size()-1));
					source = tmp;
					res.add(source);
				}else{
					System.out.println("*** /!\\ ***");
				}
			}
			return true;
		}else{
			System.out.println("Le graphe n'est pas eulerien !!");
			return false;
		}
	}

	public boolean isEulerien(){
		for (int i=0;i<listAdja.length;i++){
			if(listAdja[i].size() % 2 != 0){
				return false;
			}
		}

		return true;
	}

	public boolean parcoursLargeur(int s, int t){
		Fifo f = new Fifo();
		f.addElem(s);
		//Phase init sans l'arete (s,t)
		for (int i=0;i<listAdja[s].size();i++){
			if (listAdja[s].get(i) != t){
				f.addElem(listAdja[s].get(i));
			}
		}
		f.deleteElem();
		while(!(f.isEmpty())){
			for(int i=0; i<listAdja[f.getFirst()].size(); i++){
				if(listAdja[f.getFirst()].get(i) == t) {
					return true;
				}else{
					f.addElem(listAdja[f.getFirst()].get(i));
				}
			}
			f.deleteElem();
		}
		return false;
	}

	public int selectNextSource (int s){
		if(listAdja[s].size() == 1){
			return 0;
		}
		for(int i=0;i<listAdja[s].size();i++){
			if(listAdja[s].get(i) != sourceInit){
				return i;
			}
		}
		return -1;
	}
	
	public ArrayList<Integer> getRes() {
		return res;
	}

}
